class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();

        // 优化，哈希表存的是元素以及对应的下标值
        unordered_map<int, int> hash;
        hash[nums[0]] = 0;

        // 由题目可知：2 <= nums.length <= 1000，所以最差情况就是2，所以初始化全为2
        vector<vector<int>> dp(n, vector<int>(n, 2));

        int ret = 2;

        // 下面的填表顺序是一边dp，一边保存离他最近元素的下标
        for(int i = 1; i < n; i++)  // 先固定倒数第一个数
        {
            for(int j = i + 1; j < n; j++)  // 再固定倒数第二个数
            {
                int a = 2 * nums[i] - nums[j];  // 计算第一个数
                if(hash.count(a))
                {
                    // a存在才有研究价值
                    dp[i][j] = dp[hash[a]][i] + 1;

                    // 每一次填表，都要更新ret
                    ret = max(ret, dp[i][j]);
                }
            }

            // 每一次倒数第二个位置用完之后加入哈希表，此时之前和它相同的值就会被重新覆盖
            // 因为题目要的是最长序列，所以我们要尽可能保证序列最长，相同元素只保留最后的一个
            hash[nums[i]] = i;
        }
        return ret;
    }
};